#include<iostream>
#include<stack>
using namespace std;

/*
    定义二叉搜索树累，封装查找、插入、删除操作。
*/
template<class T>
class BinarySearchTreeNode
{
public:
    BinarySearchTreeNode<T> * leftChild;
    BinarySearchTreeNode<T> * rightChild;
    BinarySearchTreeNode<T> * parent;
    T value;
    BinarySearchTreeNode(const T & value):value(value){
        parent = NULL;
    rightChild = NULL;
    leftChild = NULL;
    }
};

template<class T>
class BinarySearchTree
{
public:
    BinarySearchTreeNode<T> * root;
    BinarySearchTree();
    ~BinarySearchTree();
    BinarySearchTreeNode<T>* search(BinarySearchTreeNode<T>* root, T key);
    void insertNode(const T& value);
    void deleteNode(int key,bool Choice);
    
    void preOrderSearch(BinarySearchTreeNode<T>* node);
    void midOrderSearch(BinarySearchTreeNode<T>* node)
    {
        if(node==NULL) return;
        midOrderSearch(node->leftChild);
        cout<<node->value<<endl;
        midOrderSearch(node->rightChild);

    }
    
};

template<class T>
BinarySearchTree<T>::BinarySearchTree()
{
    root = NULL;
    
}

template<class T>
BinarySearchTree<T>::~BinarySearchTree()
{
    while(root!=NULL) 
    {
        //cout<<"Now Root is: "<<root->value<<endl;
        deleteNode(root->value,true);
        
        
    }
    //cout<<"DeleteComplete!"<<endl;
}
//二叉搜索树的查找
template<class T>
BinarySearchTreeNode<T>* BinarySearchTree<T>::search(BinarySearchTreeNode<T>* root, T key)
{
    BinarySearchTreeNode<T> * current = root;
    
    while((root != NULL)&&(key!=current->value))
    {
        
        current = (key<current->value?search(current->leftChild,key):search(current->rightChild,key));
        
    }
    
    //cout<<"current is "<<current->value<<endl;
    return current;
    
    
}

template<class T>
void BinarySearchTree<T>::insertNode(const T& value)
{
    BinarySearchTreeNode<T> * p  = root, *prev = NULL;
    while (p!=NULL)
    {
        /* code */
        prev = p;
        if(p->value<value)
        {
            p = p->rightChild;
        }
        else p = p->leftChild;
    }
    BinarySearchTreeNode<T> * ptemp;
    if(root==NULL)  //若为空树，则建立新结点
    {
        root = new BinarySearchTreeNode<T>(value);
       root->parent = NULL;
    }
       
        
    else if(prev->value<value)
    {
        prev->rightChild = new BinarySearchTreeNode<T>(value);
        
        (prev->rightChild)->parent = prev;
    }
       
    else
    {
        prev->leftChild = new BinarySearchTreeNode<T>(value);
        (prev->leftChild)->parent = prev;
    }
        
   
    
}

//删除的算法实现
template<class T>
void BinarySearchTree<T>::deleteNode(int key,bool Choice)
{
    BinarySearchTreeNode<T> * node_delete = search(root,key);
    BinarySearchTreeNode<T> * ptemp ;
    //cout<<node_delete->value<<endl;
    if(!node_delete->rightChild)
    {
        if(node_delete==root)
        {
            root = node_delete->leftChild;
            
        }
        else if(node_delete == (node_delete->parent)->leftChild)
        {
            (node_delete->parent)->leftChild = node_delete->leftChild;
            
        }    
        else
        {
            (node_delete->parent)->rightChild = node_delete->leftChild;
            
        }
        delete node_delete;
    }
    else if(!node_delete->leftChild)
    {
        if(node_delete==root)
        {
            root = node_delete->rightChild;
            delete node_delete;
        }
        else if(node_delete == (node_delete->parent)->leftChild)
        {
            (node_delete->parent)->leftChild = node_delete->rightChild;
            
        }    
        else
        {
            (node_delete->parent)->rightChild = node_delete->rightChild;
            
        }
    
        
    }
    else
    {
        //cout<<node_delete->value<<endl;
        //cout<<"1111"<<endl;
        stack<BinarySearchTreeNode<T>*> stackForSearch;
            stackForSearch.push(node_delete->leftChild);
            
            while(stackForSearch.top()!=NULL)
            {
                ptemp = stackForSearch.top();
                stackForSearch.push(ptemp->rightChild);
            }
            stackForSearch.pop();
            if(!stackForSearch.empty())
            ptemp = stackForSearch.top();
            else
            {
                delete node_delete;
                return;
            }
            
            //cout<<node_delete->value<<endl;
            //cout<<"1112"<<endl;
            //cout<<"ptemp: "<<ptemp->value<<endl;
        if(Choice)
            
            
            {
                
               //cout<<node_delete->leftChild->value<<endl;
                if(root == node_delete) root = node_delete->leftChild;
                else if(node_delete == (node_delete->parent)->leftChild)
                {
                    (node_delete->parent)->leftChild = node_delete->leftChild;
                }    
                else 
                {
                    (node_delete->parent)->rightChild = node_delete->leftChild;
                }
                
                
            ptemp->rightChild = node_delete->rightChild;
            //cout<<"1113"<<endl;
            delete node_delete;
            }
            
            else
            {
                
            //cout<<"1114"<<endl;
            node_delete->value = ptemp->value;
            (ptemp->parent)->rightChild = ptemp->leftChild;
            delete ptemp;
            }
            
            
            
        
        
    }
    
}

template<class T> 
void BinarySearchTree<T>::preOrderSearch(BinarySearchTreeNode<T>* node)
{
    if(node == NULL) return;
    cout<<node->value<<endl;
    preOrderSearch(node->leftChild);
    preOrderSearch(node->rightChild);
}